/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/longest-substring-with-at-most-k-distinct-characters
   @Language: C++
   @Datetime: 19-03-27 11:07
   */

class Solution {
public:
	/**
	 * @param s: A string
	 * @param k: An integer
	 * @return: An integer
	 */
	int lengthOfLongestSubstringKDistinct(string &s, int k) {
		// write your code here
		unordered_map<char,int> chars;
		int len=0;
		for(int start=-1, i=0; i<s.length(); ++i){
			chars[s[i]]=i;
			if(chars.size()>k) {
				for(int j=start+1; j<i; ++j){
					if (chars[s[j]]==j){
						start=j;
						chars.erase(s[j]);
						break;
					}
				}
			}
			if(chars.size()<=k) len=len>i-start?len:i-start;
		}
		return len;
	}
};
